package exercises.leetcode;

import java.util.TreeMap;

/**
 * <a href="https://leetcode-cn.com/problems/delete-and-earn/">
 * 740. 删除并获得点数</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个整数数组 nums ，你可以对它进行一些操作。
 * <p>
 * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
 * <p>
 * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
 *
 * @author or2
 * @date 2021年09月21日 时间: 21:40
 */
public class No740 {
    public int deleteAndEarn(int[] nums) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int pre = 0;
        int preWeight = 0;
        int prePreWeight = 0;
        for (Integer num : map.keySet()) {
            int currentWeight;
            int currentPoints = num * map.get(num);
            if (num - 1 == pre) {
                currentWeight = Math.max(preWeight, prePreWeight + currentPoints);
            } else {
                currentWeight = preWeight + currentPoints;
            }
            /*滑动窗口*/
            pre = num;
            prePreWeight = preWeight;
            preWeight = currentWeight;
        }

        return preWeight;
    }
}
